package leetcode.code1856;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * 简化代码
 *
 * @author CaoYu
 * @date 2021年9月28日
 * @description
 */
public class Solution1 extends Solution1856 {

	@Override
	public int maxSumMinProduct(int[] nums) {
		int len = nums.length;
		long[] sum = new long[len + 1];// 预处理, 为了后续求[i..j]范围累加和
		for (int i = 1; i <= len; i++) {
			sum[i] = sum[i - 1] + nums[i - 1];
		}
		Stack<List<Integer>> s = new Stack<>();// 可处理重复的单调栈
		long ans = 0;
		for (int i = 0; i < len; i++) {
			while (!s.isEmpty() && nums[s.peek().get(0)] > nums[i]) {// 强迫营业 , 弹弹弹
				List<Integer> maxList = s.pop();// 栈顶列表,这些数都一样
				int left = s.isEmpty() ? 0 : s.peek().get(s.peek().size() - 1) + 1;// 左侧边界,预处理数组的下标
				ans = Math.max(ans, (sum[i] - sum[left]) * nums[maxList.get(0)]);// 结算答案
			}
			if (!s.isEmpty() && nums[s.peek().get(0)] == nums[i]) {// 相同数字进栈
				s.peek().add(i);
			} else {// 新数字进栈
				List<Integer> list = new ArrayList<>();
				list.add(i);
				s.add(list);
			}
		}
		while (!s.isEmpty()) {// 结算栈内剩余数字
			List<Integer> maxList = s.pop();
			int left = s.isEmpty() ? 0 : s.peek().get(s.peek().size() - 1) + 1;
			ans = Math.max(ans, (sum[len] - sum[left]) * nums[maxList.get(0)]);
		}
		return (int) (ans % ((int) 1e9 + 7));
	}

	public static void main(String[] args) {
		Solution1 so = new Solution1();
		so.debug1();
		so.debug2();

	}

}
